/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 殇
 * Date: 2025-08-01
 * Time: 10:27
 */
import java.util.Arrays;

public class PriorityQueue {
    //对于节点i，其父节点的位置为: (i-1)/2
    //             左孩子的位置为: 2*i+1 ;  右孩子的位置为: 2*i+2
    //size: 表示当前有效的数据，如果一个节点的位置 i>size => 表示位置不存在,非法位置
    public int[] elem;
    public int size;     //实际大小

    private void swap(int[] arr,int i,int j) {
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    public PriorityQueue() {
        elem=new int[11];
    }

    //建堆的时间复杂度：O(n),尤其注意!!!
    public void createHeap(int[] array) {

        for(int i=0;i<array.length;i++) {
            elem[i]=array[i];
            size++;
        }
        for(int i=(size-1-1)/2;i>=0;i--) {
            shiftDown(i, size);
        }
    }

    //i为要调整的位置
    //size为数组实际大小
    //向下调整的时间复杂度：O(logn)
    private void shiftDown(int i,int size) {
        int child=2*i+1;
        while(child<size) {  //只有节点有孩子就进循环
            //获取孩子节点最大值所在下标
            //1.如果无右孩子=》index=child
            //2.有左右孩子  =》index=elem[child]<elem[child+1]?child+1:child
            int maxPos=(child+1<size)&&(elem[child]<=elem[child+1])?child+1:child;
            //如果已经是大根堆，则无需调整
            if(elem[maxPos]<=elem[i]) {
                break;
            }
            //节点交换，位置更新
            swap(elem,i,maxPos);
            i=maxPos;
            child=2*i+1;
        }
    }

    //向上调整算法: 只要不满足条件，就交换元素，一直向上，直到满足条件
    private void shiftUp(int i) {
        int parent=(i-1)/2;
        while(parent>=0) {
            if(elem[i]>elem[parent]) {  //如果i节点>父节点，交换，直到满足条件
                swap(elem,i,parent);
                i=parent;
                parent=(i-1)/2;
            }
            else {
                break;
            }
        }
    }
    //入队：仍然要保持是大根堆
    public void push(int val) {
        if(isFull()) {
            elem=Arrays.copyOf(elem,2*elem.length);
        }
        elem[size]=val;
        //插入完向上调整到适合位置
        shiftUp(size);
        size++;
    }



    public boolean isFull() {
        return size==elem.length;
    }

    //出队【删除】：每次删除的都是优先级高的元素
    //仍然要保持是大根堆
    public int pollHeap() {
        if(isEmpty()) {
            return -1;
        }
        int ret=elem[0];
        swap(elem,0,size-1);
        size--;
        shiftDown(0,size);
        return ret;
    }

    public boolean isEmpty() {
        return size==0?true:false;
    }

    //获取堆顶元素
    public int peekHeap() {
        if(isEmpty()) {
            return -1;
        }
        return elem[0];
    }
    public static void main(String[] args) {
        int[] array=new int[] {21,13,7,9,3,17,27,20,1,6,25};
        PriorityQueue priorityQueue=new PriorityQueue();
        priorityQueue.createHeap(array);
        for(int i=0;i<array.length;i++) {
            System.out.print(priorityQueue.pollHeap()+" ");
        }
    }
}